package com.ctrip.demo.leetcode;

import java.util.ArrayList;
import java.util.List;

public class Leetcode648 {

    public static void main(String[] args) {
        ArrayList<String> objects = new ArrayList<>();
        objects.add("cat");
        objects.add("bat");
        objects.add("rat");

        System.out.println(new Leetcode648().replaceWords(objects, "the cattle was rattled by the battery"));

    }

    class Node {
        boolean isEnd;
        Node[] tns = new Node[26];
    }

    Node root = new Node();
    void add(String s) {
        Node p = root;
        for(int i = 0; i < s.length(); i ++) {
            int u = s.charAt(i) - 'a';
            if (p.tns[u] == null) {
                p.tns[u] = new Node();
            }
            p = p.tns[u];
        }
        p.isEnd = true;
    }

    String query(String s) {
        Node p = root;
        for(int i = 0; i < s.length(); i ++) {
            int u = s.charAt(i) - 'a';
            if (p.tns[u] == null) {
                break;
            }
            if (p.tns[u].isEnd) {
                return s.substring(0, i + 1);
            }
            p = p.tns[u];
        }
        return s;
    }
    public String replaceWords(List<String> dictionary, String sentence) {
        for (String s : dictionary) {
            add(s);
        }
        StringBuilder res = new StringBuilder();
        for (String s : sentence.split(" ")) {
            res.append(query(s)).append(" ");
        }
        return res.substring(0, res.length() - 1);
    }

}
